package com.ww.springboot.boot.algorithm.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 接雨水
 * --添加图形化
 * <p>
 * pop :出栈
 * peek :取栈顶元素
 *
 * @author wanwei
 * @since 2021-04-17 17:03
 */
public class TrapWithPaintDemo {

    public static void main(String[] args) {
        /*int[] array = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        method(array);
        int[] array2 = {4, 2, 0, 3, 2, 5};
        method(array2);
        int[] array3 = {4, 2, 3};
        method(array3);
        int[] array4 = {5, 2, 1, 2, 1, 5};
        method(array4);*/
        int[] array5 = {6, 4, 2, 0, 3, 2, 0, 3, 1, 4, 5, 3, 2, 7, 5, 3, 0, 1, 2, 1, 3, 4, 6, 8, 1, 3};
        method(array5);
    }

    private static void method(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            if (max < height[i]) {
                max = height[i];
            }
        }

        String[][] ss = whitePaint(height, max);
        List<String> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> index = new Stack<>();
        int total = 0;
        int nextNumMax = 0;
        //1.遍历
        for (int i = 0; i < height.length; i++) {
            //将数字入栈
            int num = height[i];
            if (stack.empty() || num < stack.peek()) {
                stack.push(num);
                index.push(i);
            } else {
                //取出栈顶元素
                while (!stack.empty()) {
                    if (stack.peek() == 0) {
                        stack.pop();
                        index.pop();
                        continue;
                    }
                    if (num >= stack.peek()) {
                        int pop = stack.pop();
                        int indexValue = index.pop();

                        if (i - indexValue - 1 > 0 && (pop - nextNumMax) > 0) {
                            //添加【储水空间】
                            total += (i - indexValue - 1) * (pop - nextNumMax);
                            list.add(i + "*" + indexValue + "*" + pop + "*" + nextNumMax);
                        }

                        if (nextNumMax < pop) {
                            nextNumMax = pop;
                        }
                    } else {
                        stack.peek();
                        int indexValue = index.peek();
                        if (i - indexValue - 1 > 0 && (num - nextNumMax) > 0) {
                            //添加【储水空间】
                            total += (i - indexValue - 1) * (num - nextNumMax);
                            list.add(i + "*" + indexValue + "*" + num + "*" + nextNumMax);
                        }
                        break;
                    }
                }
                //栈空时，清空上一个栈值
                nextNumMax = 0;
                stack.push(num);
                index.push(i);
            }
        }
        whitePaintAll(ss, list, max);
        System.out.println("-------------------总空间为：" + total + "----------");
        System.out.println(list.toString());
    }

    private static void whitePaintAll(String[][] ss, List<String> list, int max) {
        System.out.println("-------------------标记后--------------------");
        char n = 'A';
        for (String s : list) {
            String[] array = s.split("\\*");
            int xEnd = Integer.parseInt(array[0]);
            int xStart = Integer.parseInt(array[1]);

            int yEnd = Integer.parseInt(array[2]);
            int yStart = Integer.parseInt(array[3]);
            for (int i = xStart + 1; i < xEnd; i++) {
                for (int j = yStart; j < yEnd; j++) {
                    ss[i][max - j - 1] = String.valueOf(n);
                }
            }
            n++;
        }
        printArray(ss, max);
    }

    private static void printArray(String[][] ss, int max) {
        for (int j = 0; j < max; j++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < ss.length; i++) {
                stringBuilder.append(ss[i][j]);
            }
            System.out.println(stringBuilder);
        }
    }


    private static String[][] whitePaint(int[] height, int max) {
        System.out.println("-------------------数状图--------------------");
        String[][] ss = new String[height.length][max];
        for (int i = 0; i < height.length; i++) {
            for (int j = max; j > 0; j--) {
                if (height[i] < j) {
                    ss[i][max - j] = " ";
                } else {
                    ss[i][max - j] = "*";
                }
            }
        }
        printArray(ss, max);
        return ss;
    }
}
